package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         91,
		Discription: "数字字符串到字母映射的种类数",
		Level:       2,
		Labels: map[string]int{
			"动态规划": 1,
		},
	})
}

func NumDecodings(s string) int {
	dp := make([]int, len(s)+1)
	if s[0]-'0' == 0 {
		return 0
	}

	//dp[i]表示s[0:i]的映射种类数
	//注意dp[0] = 1，考虑到dp[2]前两个数字映射为一个字母的情况
	dp[0] = 1
	dp[1] = 1

	for i := 2; i <= len(s); i++ {
		if dp[i-1] == 0 {
			return 0
		}

		count := 0
		num := s[i-1] - '0'
		if num != 0 {
			count += dp[i-1]
		}

		num2 := s[i-2] - '0'
		index := num2*10 + num
		if index >= 10 && index <= 26 {
			count += dp[i-2]
		}

		dp[i] = count
	}

	return dp[len(s)]
}
